package com.cjl.dmsxl.backtrack;

import org.junit.jupiter.api.Test;

import java.util.*;

public class BackTrackPractice {

    /**
     * 77. 组合
     *
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        // 结果集
        List<List<Integer>> res = new ArrayList<>();
        // 每一次的结果
        List<Integer> path = new ArrayList<>();
        combineBackTrack(n, k, 1, path, res);
        return res;
    }

    private void combineBackTrack(int n, int k, int startIndex, List<Integer> path, List<List<Integer>> res) {
        // 终止条件
        if (path.size() == k) {
            // 收集结果
            res.add(new ArrayList<>(path));
            return;
        }
        // 处理当前层逻辑
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 剪枝优化
            // 添加到path
            path.add(i);
            // 递归,注意递归传递的startIndex是i + 1,代表下一轮递归从下一个数开始
            combineBackTrack(n, k, i + 1, path, res);
            // 回溯
            path.remove(path.size());
        }
    }

    /**
     * 216. 组合总和 III
     *
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        // 结果集
        List<List<Integer>> res = new ArrayList<>();
        // 每一次的结果
        List<Integer> path = new ArrayList<>();
        combinationSum3BackTrack(k, n, 1, 0, res, path);
        // 返回结果集
        return res;
    }

    private void combinationSum3BackTrack(
            int k, int n, int startIndex, int sum, List<List<Integer>> res, List<Integer> path) {
        // 剪枝操作，如果sum大于targetSum就停止
        if (sum > n) {
            return;
        }
        // 递归终止条件
        if (k == path.size()) {
            if (sum == n) {
                res.add(new ArrayList<>(path));
            }
            return;
        }
        // 单层for循环增加path结果
        // 单元组合元素从1-9中取值
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 减枝
            sum += i;
            path.add(i);
            // 递归
            combinationSum3BackTrack(k, n, i + 1, sum, res, path);
            // 回溯
            sum -= i;
            path.remove(path.size() - 1);
        }
    }

    /**
     * 17. 电话号码的字母组合
     *
     * @param digits
     * @return
     */
    public List<String> letterCombinations(String digits) {
        // 排除空字符串情况
        if (digits.length() == 0) {
            return List.of();
        }
        // 定义数组快速查询每个数字所对应的字符串
        String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        // 结果集
        ArrayList<String> res = new ArrayList<>();
        // 单个结果
        StringBuilder path = new StringBuilder();
        // 递归
        letterCombinationsBackTrack(digits, map, 0, res, path);
        return res;
    }

    private void letterCombinationsBackTrack(
            String digits, String[] map, int index, ArrayList<String> res, StringBuilder path) {
        // 终止条件，当递归层数达到目标目标长度时就可以收集结果
        if (index == digits.length()) {
            res.add(path.toString());
            return;
        }
        // 获取当前数字做对应的字符串
        String str = map[digits.charAt(index) - '0'];
        // 单层for循环收集结果
        for (int i = 0; i < str.length(); i++) {
            path.append(str.charAt(i));
            // 递归，注意递归层数需要加一
            letterCombinationsBackTrack(digits, map, index + 1, res, path);
            // 回溯
            path.deleteCharAt(path.length() - 1);
        }
    }

    /**
     * 39. 组合总和
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        // 排序数组用于减枝操作
        Arrays.sort(candidates);
        combinationSumBackTrack(candidates, target, 0, res, path);
        return res;
    }

    private void combinationSumBackTrack(int[] candidates, int target, int startIndex, List<List<Integer>> res, List<Integer> path) {
        // 收集结果
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            //  减枝优化，此处必须写上，避免重复递归
            if (target - candidates[i] < 0) {
                break;
            }
            path.add(candidates[i]);
            combinationSumBackTrack(candidates, target - candidates[i], i, res, path);
            path.remove(path.size() - 1);
        }
    }

    /**
     * 40. 组合总和 II
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        // used数组对数层进行去重
        boolean[] used = new boolean[candidates.length];
        // 对数组进行排序剪枝
        Arrays.sort(candidates);
        combinationSum2BackTrack(candidates, target, 0, used, res, path);
        return res;
    }

    private void combinationSum2BackTrack(int[] candidates, int target, int startIndex, boolean[] used, ArrayList<List<Integer>> res, LinkedList<Integer> path) {
        // 递归终止条件
        if (target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 单层回溯逻辑
        for (int i = startIndex; i < candidates.length; i++) {
            // 减枝
            if (target - candidates[i] < 0) {
                break;
            }
            // 对同一数层的元素进行去重
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
                continue;
            }
            // 更新used数组
            used[i] = true;
            path.add(candidates[i]);
            // 递归
            combinationSum2BackTrack(candidates, target - candidates[i], i + 1, used, res, path);
            // 回溯
            used[i] = false;
            path.removeLast();
        }
    }

    /**
     * 131. 分割回文串
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        ArrayList<List<String>> res = new ArrayList<>();
        ArrayList<String> path = new ArrayList<>();
        partitionBackTrack(s, 0, res, path);
        return res;
    }

    private void partitionBackTrack(String s, int startIndex, ArrayList<List<String>> res, ArrayList<String> path) {
        // 当分割到最后一位的时候就终止，并收集结果
        if (startIndex >= s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 单层循环
        for (int i = startIndex; i < s.length(); i++) {
            String str = s.substring(startIndex, i + 1);
            if (isPalindrome(str)) {
                // 是一个回文串，加入集合
                path.add(str);
            } else {
                // 如果不是回文串就跳过本次循环
                continue;
            }
            // 此时一定是回文串
            partitionBackTrack(s, i + 1, res, path);
            path.remove(path.size() - 1);
        }
    }

    private boolean isPalindrome(String str) {
        for (int i = 0, j = str.length() - 1; i < j; i++, j--) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 93. 复原 IP 地址
     * @param s
     * @return
     */
    public List<String> restoreIpAddresses(String s) {
        ArrayList<String> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder(s);
        restoreIpAddressesBackTrack(sb, 0, 0, res);
        return res;
    }

    private void restoreIpAddressesBackTrack(StringBuilder sb, int startIndex, int pointNum, ArrayList<String> res) {
        // 递归终止条件：如果点的数量==3并且当前字符串合法则收集结果
        if (pointNum == 3) {
            if (isIpValid(sb,startIndex,sb.length() - 1)) {
                // 收集结果
                res.add(sb.toString());
            }
            // 终止递归
            return;
        }
        // 单层递归逻辑
        for (int i = startIndex; i < sb.length(); i++) {
            // 判断当前字符串是否合法
            if (isIpValid(sb,startIndex,i)) {
                // 加入点
                sb.insert(i + 1, '.');
                // 递归,由于加入了一个点，所以递归开始位置要从i + 2开始，同时点的数量加一
                restoreIpAddressesBackTrack(sb, i + 2, pointNum + 1, res);
                // 回溯,删除这个点
                sb.deleteCharAt(i + 1);
            } else {
                // 如果字符非法则直接终止本层循环，后面的也不用看了
                break;
            }
        }

    }

    // 判断ip是否合法
    private boolean isIpValid(StringBuilder sb, int start, int end) {
        if (start > end) {
            return false;
        }
        if (sb.charAt(start) == '0' && start != end) {
            return false;
        }
        long num = Long.parseLong(sb.substring(start, end + 1));
        if (num > 255) {
            return false;
        }
        return true;
    }

    /**
     * 78. 子集
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        // 结果集
        List<List<Integer>> res = new ArrayList<>();
        // 每一层递归的结果
        List<Integer> path = new ArrayList<>();
        // 递归收集结果
        subsetsBackTrack(nums, 0, res, path);
        // 返回结果
        return res;
    }

    private void subsetsBackTrack(int[] nums, int startIndex, List<List<Integer>> res, List<Integer> path) {
        // 一开始就收集一次结果，以免漏掉空集
        res.add(new ArrayList<>(path));
        // 终止条件：递归到最底层也就是startIndex == nums.length,就终止
        if (startIndex == nums.length) {
            return;
        }
        // 单层递归逻辑
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            subsetsBackTrack(nums, i + 1, res, path);
            path.remove(path.size() - 1);
        }
    }

    @Test
    public void test() {
        System.out.println(restoreIpAddresses("0279245587303"));
    }


}
